package LeetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}10:09
 */
public class LeetCode377 {
    // 方法一：使用单纯的递归 会出现重复的情况 需要使用记忆集来
    private static List<List<Integer>> res = new ArrayList<>();
    public int combinationSum4(int[] nums, int target) {
        if (nums.length == 0){
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        dfs(nums,target,list);
        return res.size();
    }

    public void dfs(int[] nums,int target,List<Integer> list){
        if (target == 0){
            res.add(new ArrayList<>(list));
            return;
        }
        if (target < 0){
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (nums[i] <= target){
                list.add(nums[i]);
                dfs(nums,target - nums[i],list);
                list.remove(list.size() - 1);
            }
        }
    }


    /**
     * 动态规划 全背包
     * 这里状态定义就是题目要求的，并不难，状态转移方程要动点脑子，也不难：
     * 状态转移方程：dp[i]= dp[i - nums[0]] + dp[i - nums[1]] + dp[i - nums[2]] + ... （当 [] 里面的数 >= 0）
     * 特别注意：dp[0] = 1，表示，如果那个硬币的面值刚刚好等于需要凑出的价值，这个就成为 1 种组合方案
     * 再举一个具体的例子：nums=[1, 3, 4], target=7;
     * dp[7] = dp[6] + dp[4] + dp[3]
     * 即：7 的组合数可以由三部分组成，1 和 dp[6]，3 和 dp[4], 4 和dp[3];
     *
     * @param nums
     * @param target
     * @return
     */

    public int combinationSum42(int[] nums, int target){
            int[] dp = new int[target + 1];
            // 这个值被其它状态参考，设置为 1 是合理的
            dp[0] = 1;

            for (int i = 1; i <= target; i++) {
                for (int num : nums) {
                    if (num <= i) {
                        dp[i] += dp[i - num];
                    }
                }
            }
            return dp[target];
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode377().combinationSum42(new int[]{1,2,3}, 4));
        System.out.println(res.toString());
    }

}
